# LeetCode 126. 单词接龙 II
# https://leetcode.cn/problems/word-ladder-ii/description/
import copy
from collections import deque
from math import inf
from typing import List


class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        result = []
        if endWord not in wordList:
            return result

        def is_similiar(word0, word1):
            not_same = 0
            for i in range(len(word0)):
                if word0[i] != word1[i]:
                    not_same += 1
            return not_same

        if beginWord not in wordList:
            wordList.append(beginWord)
        adj = {word: [] for word in wordList}
        for i, word0 in enumerate(wordList):
            for j in range(i + 1, len(wordList)):
                word1 = wordList[j]
                if is_similiar(word0, word1) == 1:
                    adj[word0].append(word1)
                    adj[word1].append(word0)

        def bfs(s, dest):
            d = {word: inf for word in wordList}
            d[s] = 0
            q = deque()
            q.append(s)
            while q:
                u = q.popleft()
                if u == dest:
                    # print(d)
                    return d, d[u]
                for v in adj[u]:
                    if d[v] == inf:
                        d[v] = d[u] + 1
                        q.append(v)
            return None, None

        forwardpath, min_length = bfs(beginWord, endWord)
        backwardpath, min_length = bfs(endWord, beginWord)
        if min_length == None:
            return result

        def dfs(word):
            stack.append(word)
            if word == endWord:
                tmp = copy.deepcopy(stack)
                result.append(tmp)
            for v in adj[word]:
                if forwardpath[v] + backwardpath[v] == min_length and forwardpath[v] == forwardpath[word] + 1:
                    if len(stack) != forwardpath[v]:
                        del stack[forwardpath[v]:]
                    dfs(v)

        stack = [beginWord]
        dfs(beginWord)
        return result


if __name__ == '__main__':
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot", "dot", "dog", "lot", "log", "bot", "cog"]
    beginWord = "a"
    endWord = "c"
    wordList = ["a", "b", "c"]
    beginWord = "hot"
    endWord = "dog"
    wordList = ["hot", "dog"]
    beginWord = "hot"
    endWord = "dog"
    wordList = ["hot", "dog", "dot"]
    print(Solution().findLadders(beginWord, endWord, wordList))
